#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.geeksforgeeks.org/check-if-the-given-push-and-pop-sequences-of-stack-is-valid-or-not/
"""


def is_valid_pop_order(in_order, out_order):
    # NOTE: 1: 考虑in_order 元素个数 > out_order,
    # NOTE: 2: 考虑in_order 元素个数 < out_order,
    cur_stack = []
    copy_out_order = list(out_order)

    for ele in in_order:
        cur_stack.append(ele)

        if not copy_out_order:
            break

        while cur_stack and cur_stack[-1] == copy_out_order[0]:
            cur_stack.pop()
            copy_out_order.pop(0)

    # 空返回True, 非空返回False
    return not cur_stack and not copy_out_order

def main():
    print("start main")
    valid = is_valid_pop_order("abcde", "abcde")
    assert(valid)

    valid = is_valid_pop_order("abcde", "abced")
    assert(valid)

    valid = is_valid_pop_order("abcde", "cab")
    assert(not valid)

    valid = is_valid_pop_order("abc", "abcde")
    assert(not valid)

    in_order   = [5, 9, 1, 8, 13, 4, 2, 7]
    out_order1 = [8, 4, 13, 1, 7, 2, 9, 5]
    out_order2 = [8, 4, 13, 1, 5, 2, 7, 9]

    valid = is_valid_pop_order(in_order, out_order1)
    assert(valid)

    valid = is_valid_pop_order(in_order, out_order2)
    assert(not valid)

    valid = is_valid_pop_order("12345", "43512")
    assert(not valid)

    # pPush中序列为：[5   9   1   8    13     4   2    7]
    # 给出一个出栈序列pPop：[8   4    13   1   7   2  9   5]，这个出栈序列是正确的。
    # 给出另一个出栈序列pPop:[8   4    13   1   5   2     7    9]，这个出栈序列就是错误的，因为8第一个出栈，说明栈中已经压入过5  9  1三个元素，它们还存在栈中


if __name__ == "__main__":
    main()
